The invention relates generally to parallel data processing methods and apparatus and in particular to an instruction execution method and apparatus for increasing the efficiency of instruction execution in a parallel processing computer.
In a parallel processing computer wherein high efficiency requires the ability to process, during a single machine cycle, a plurality of instructions, the number of instructions being for example on the order of ten or twenty, a limiting factor has been the ability to compact operations which include conditional jumps or branches. Conditional jumps occur, statistically, every five to eight instructions in a typical sequential program; and therefore, to compact more than five or so operations in one machine cycle requires the capability of handling more than one conditional jump in the single machine cycle. Typically, however, compaction ceases at a conditional jump and once the conditional (or unconditional) jump was taken, compaction can then proceed again.
In a very long instruction word machine such as that described hereinafter, a multiprocessor is capable of handling 1,024 bits of instruction each clock cycle. If that equipment is to use its resources fully, multiple conditional jumps must be compacted into a single instruction. The difficulty arises with respect to how to properly execute those multiple jumps.
Clearly one cannot perform the jumps sequentially and maintain the parallelism for which the multiprocessor was designed. On the other hand, to do all the jumps simultaneously seems a hopeless problem with regard to determining which jump to take and when conditions should be tested.
Therefore, objects of the present invention are to enable a data processing method and apparatus which can compact sequential code, including several conditional jumps or branches, for execution in a single computer machine cycle, and to reliably compact more than five to eight instructions in a single machine cycle. Other objects of the invention include a compacting method and apparatus for selecting and simultaneously executing conditional branch instructions in a VLIW computer having the capability of executing up to twenty or more instructions in one machine cycle. Further objects of the invention are a multiple branch parallel computing method and apparatus which reliably handle multiple conditional branches in a single machine cycle and which do not require additional machine cycles to effect the correct branch selection.